package com.yuufa.test.ex;

public class Ex9 {

    public static void main(String[] args) {

    }
}

// sort
class S1 {
    public static void sort(int[] s, int n) {
        for(int i=n-1;i>=0;i--) {
            for(int j=0;j<i;j++) {
                if(s[j] > s[j+1]) {
                    int t = s[j]; s[j] = s[j+1]; s[j+1] = t;
                }
            }
        }
    }
}

class S2 {
    public static void sort(int[] s, int n) {
        for(int i=0;i<n;i++) {
            int t = s[i];
            int j = i - 1;
            while(j>=0 && t<s[j]) {
                s[j+1] = s[j];
                j--;
            }
            s[j+1] = t;
        }
    }
}

class S3 {
    public static void sort(int[] s, int n) {
        for(int gap=n/2;gap>=1;gap/=2) {
            for(int i=gap;i<n;i++) {
                int t = s[i];
                int j = i-gap;
                while(j>=0 && t<s[j]) {
                    s[j+gap] = s[j];
                    j-=gap;
                }
                s[j+gap] = t;
            }
        }
    }
}

class S4 {
    public static void _sort(int[] s, int n ) {
        for(int i=n-1;i>=0;i--) {
            int j=i;
            for(int k=0;k<i;k++) {
                if(s[k]>s[j]) {
                    j=k;
                }
            }
            int t = s[i]; s[i] = s[j]; s[j] = t;
        }
    }
    
    public static void sort(int[] s, int n) {
        for(int i=0;i<n;i++) {
            int j = i;
            for(int k=i+1;k<n;k++) {
                if(s[j]>s[k]) {
                    j = k;
                }
            }
            int t = s[i]; s[i] = s[j]; s[j] = t;
        }
    }
}

class S5 {
    public static void sort(int[] s, int left, int right, int n) {
        if(left<=right) {
            int k = partition(s, left, right, n);
            sort(s, left, k-1, n);
            sort(s, k+1, right, n);
        }
    }
    
    public static int partition(int[] s, int left, int right, int n) {
        int pivot = s[left];
        int i = left;
        int j = right + 1;
        
        while(i<j) {
            while(++i<=right && s[i]<pivot);
            while(--j>=left && s[j]>pivot);
            
            if(i<j) {
                int t = s[i]; s[i] = s[j]; s[j] = t;
            }
        }
        
        s[left] = s[j]; s[j] = pivot;
        
        return j;
    }
}

class S6 {
    
    public static void shift(int[] s, int index, int n) {
        int j = 2 * index;
        
        while(j<=n) {
            if(j<n) {
                if(s[j] < s[j+1]) {
                    j++;
                }
            }
            
            if(s[index]<s[j]) {
                s[j/2] = s[j];
                j=j*2;
            } else {
                break;
            }
        }
        s[j/2] = s[index];
    }
    
    public static void sort(int[] s, int n) {
        for(int i=n/2;i>=1;i--) {
            shift(s, i, n);
        }
        
        int t = s[1]; s[1] = s[n]; s[n] = t;
        
        for(int i=n-1;i>=1;i--) {
            shift(s, 1, i);
            t = s[1]; s[1] = s[i]; s[i] = t;
        }
    }
}

class S7 {
    public static void sort(int[] s1, int n1, int[] s2, int n2) {
        int[] s = new int[n1+n2];
        int i=0,j=0,k=0;

        while(i<=n1 && j<=n2) {
            if(s1[i]<s2[j]) {
                s[k++] = s1[i++];
            } else if ( s1[i]>s2[j] ) {
                s[k++] = s2[j++];
            }
        }
        
        while(i<=n1) {
            s[k++] = s1[i++];
        }
        
        while(j<=n2) {
            s[k++] = s2[j++];
        }
    }
}

// linear search
class LinearSearchMain {
    public static int search(int[] s, int key, int n) {
        for(int i=0;i<n;i++) {
            if( key == s[i] ) {
                return i;
            }
        }
        
        return -1;
    }
}

// binary search 
class BinarySearchMain {
    public static int _search(int[] s, int left, int right, int key) {
        if( left <= right ) {
            int mid = ( left + right ) / 2;
            if( key == s[mid]) {
                return mid;
            } else if ( key > s[mid] ) {
                return _search(s, mid+1, right, key);
            } else if ( key < s[mid] ) {
                return _search(s, left, mid-1, key);
            }
        }
        
        return -1;
    }
    
    public static int search(int[] s, int left, int right, int key) {
        while(left<=right) {
            int mid = ( left + right ) / 2;
            if( key == s[mid] ) {
                return mid;
            } else if ( key > s[mid] ) {
                left = mid + 1;
            } else if ( key < s[mid] ) {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

// recursive
class FibMain {
    public static void fib(int n) {
        int[] s = new int[n];
        s[0] = 0; s[1] = 1;
        
        for(int i=2;i<=n;i++) {
            s[i] = s[i-1] + s[i-2];
        }
    }
}

// stack
class StackMain {
    
    static int sp;
    static int n;
    static int[] s = new int[n];
    
    public static boolean isEmpty() {
        return sp == -1;
    }
    
    public static boolean isFull() {
        return sp == (n-1);
    }
    
    public static void push(int v) throws Exception {
        if( isFull() ) {
            throw new Exception();
        } else {
            s[++sp] = v;
        }
    }
    
    public static int pop() throws Exception {
        
        if( isEmpty() ) {
            throw new Exception();
        } else {
            return s[sp--];
        }
    }
    
    public static int top() throws Exception {
        if( isEmpty() ) {
            throw new Exception();
        } else {
            return s[sp];
        }
    }
}

// linear queue
// move()
class LinearQueueMain {
    
    static int n;
    static int[] s = new int[n];
    static int front = -1;
    static int rear = -1;
    
    public static boolean isEmpty() {
        return front == rear;
    }
    
    public static boolean isFull() {
        return front == -1 && rear == (n-1);
    }
    
    public static void move() {
        for(int i=front+1;i<=rear;i++) {
            s[i-front-1] = s[i];
        }
        rear = rear-front-1;
        front = -1;
    }
    
    public static void enqueue(int v) throws Exception {
        if( isFull() ) {
            throw new Exception("queue is full");
        } else {
            if( rear == (n-1) ) {
                move();
            } else {
                s[++rear] = v;
            }
        }
    }
    
    public static int dequeue() throws Exception {
        if( isEmpty() ) {
            throw new Exception("queue is empty");
        } else {
            return s[++front];
        }
    }
    
    public static int top() throws Exception {
        if( isEmpty() ) {
            throw new Exception("queue is empty");
        } else {
            return s[front + 1];
        }
    }
}

// circular queue

// special circular queue